/**
 * @file 八皇后问题，题目：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。
 * @author
 */

const getChessBoard = (size = 8) => {
    let chessBord = [];
    for (let i = 0; i < size; i++) {
        chessBord.push(Array(size).fill(0));
    }
    return chessBord;
    // return [
    //     [1, 0, 0, 0, 0, 0, 0, 0],
    //     [0, 0, 0, 1, 0, 0, 0, 0],
    //     [0, 1, 0, 0, 0, 0, 0, 0],
    //     [0, 0, 0, 0, 0, 0, 0, 0],
    //     [0, 0, 1, 0, 0, 0, 0, 0],
    //     [0, 0, 0, 0, 0, 0, 0, 0],
    //     [0, 0, 0, 0, 0, 0, 0, 0],
    //     [0, 0, 0, 0, 0, 0, 0, 0]
    // ];
};

const hasClash = (chessBord, x, y) => {
    const len = chessBord.length;
    for (let i = 0; i < len; i++) {
        const rowHasClash = chessBord[x][i] === 1;
        const colHasClash = chessBord[i][y] === 1;
        const directions = [
            [1, 1],
            [1, -1],
            [-1, 1],
            [-1, -1]
        ];
        // 四向斜线有没有冲突
        const slashHasClash = directions.some(([xMark, yMark]) => {
            const newX = x + xMark * (i + 1);
            const newY = y + yMark * (i + 1);
            return chessBord[newX] && chessBord[newX][newY] === 1;
        });
        if (rowHasClash || colHasClash || slashHasClash) {
            return false;
        }
    }
    return true;
};

// 栈问题 或 递归问题
// const dfs = (待遍历的树, 递归深度) => {
// 
//     if (递归深度 || 找到了结果) {
//         // 终结点!
//     }
// 
//     for (走掉你的当前这次所有可能性) {
//         把这次的可能性做实
//         dfs();
//         这次完成后，还原，走下一个兄弟节点的可能性
//     }
// };

let count = 0;
// 在当前列，下棋子
const drop = (chessBord, depth, maxDepth) => {

    if (depth >= maxDepth) {
        console.log('chessBord - in:');
        for (let i = 0; i < maxDepth; i++) {
            console.log(chessBord[i]);
        }
        count++;
        return;
    }
 
    for (let i = 0; i < maxDepth; i++) {
        // ???? 判断横行，纵行，斜行有没有棋子
        if (hasClash(chessBord, depth, i)) {
            chessBord[depth][i] = 1;
            drop(chessBord, depth + 1, maxDepth);
            chessBord[depth][i] = 0;
        }
    }
};

const start = () => {
    const chessBoard = getChessBoard(8);
    drop(chessBoard, 0, chessBoard.length);
    console.log('count - is:', count);
};

start();
